/**
 * 面试题 01.05. 一次编辑
 * https://leetcode-cn.com/problems/one-away-lcci/
 */
public class Solutions_mianshi_01_05 {
    public static void main(String[] args) {
        String first = "pale", second = "ple";  // output: true
//        String first = "pales", second = "pal";  // output: false
//        String first = "a", second = "b";  // output: true
//        String first = "teacher", second = "beacher";  // output: true

        boolean result = oneEditAway(first, second);
        System.out.println(result);
    }

    /**
     * 解法二：双指针
     */
    public static boolean oneEditAway(String first, String second) {
        int len1 = first.length(), len2 = second.length();
        if (Math.abs(len1 - len2) > 1) {
            // 关键：字符串长度之差小于等于 1
            return false;
        }
        int notSameCnt = 0;
        char[] arr1 = first.toCharArray(), arr2 = second.toCharArray();
        int i = 0, j = 0;
        while (i < len1 && j < len2) {
            if (arr1[i] != arr2[j]) {
               notSameCnt ++;
               if (notSameCnt > 1) {
                   return false;
               }
               // 若字符串相等，当前字符不同时，用掉一次编辑的机会，继续遍历后续字符
               if (len1 != len2) {
                   // 两字符串长度不等时，长度较短的字符串索引减 1 继续比较
                   if (len1 < len2) {
                       // "ple" 与 "pale" 的情况
                       i --;
                   } else {
                       // "pale" 与 "ple" 的情况
                       j --;
                   }
               }
            }
            i ++;
            j ++;
        }
        return true;
    }

    /**
     * 解法一：动态规划
     * 状态转移方程
     * 若 arr1[i] == arr2[j]，则 dp[i][j] = dp[i - 1][j - 1]
     * 否则 dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1
     */
    public static boolean oneEditAway2(String first, String second) {
        int len1 = first.length(), len2 = second.length();
        if (Math.abs(len1 - len2) > 1) {
            return false;
        }
        // dp[4][3] = 1：表示字符串 first 前 4 个字符与 second 前 3 个字符只需编辑 1 次使其相等
        int[][] dp = new int[len1 + 1][len2 + 1];
        char[] arr1 = first.toCharArray(), arr2 = second.toCharArray();
        // 初始化 dp 数组
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (arr1[i - 1] == arr2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int temp = Math.min(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = Math.min(dp[i - 1][j - 1], temp) + 1;
                }
            }
        }
        return dp[len1][len2] <= 1;
    }
}
